package com.hy;

import java.util.HashMap;
import java.util.Map;


/**
 * Created With IntelliJ IDEA.
 * Descriptions:最多 K 个重复元素的最长子数组
 *
 * 给你一个整数数组 nums 和一个整数 k 。
 * 一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。
 * 如果一个数组中所有元素的频率都 小于等于 k ，那么我们称这个数组是 好 数组。
 * 请你返回 nums 中 最长好 子数组的长度。
 * 子数组 指的是一个数组中一段连续非空的元素序列。
 *
 * 示例 1：
 * 输入：nums = [1,2,3,1,2,3,1,2], k = 2
 * 输出：6
 * 解释：最长好子数组是 [1,2,3,1,2,3] ，值 1 ，2 和 3 在子数组中的频率都没有超过 k = 2 。[2,3,1,2,3,1] 和 [3,1,2,3,1,2] 也是好子数组。
 * 最长好子数组的长度为 6 。
 *
 * 示例 2：
 * 输入：nums = [1,2,1,2,1,2,1,2], k = 1
 * 输出：2
 * 解释：最长好子数组是 [1,2] ，值 1 和 2 在子数组中的频率都没有超过 k = 1 。[2,1] 也是好子数组。
 * 最长好子数组的长度为 2 。
 *
 * 示例 3：
 * 输入：nums = [5,5,5,5,5,5,5], k = 4
 * 输出：4
 * 解释：最长好子数组是 [5,5,5,5] ，值 5 在子数组中的频率没有超过 k = 4 。
 * 最长好子数组的长度为 4 。
 *
 *
 * 提示：
 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 109
 * 1 <= k <= nums.length
 *
 * <p>
 * User:Mr.Du
 * Date:2024/4/1
 * Time:11:10
 */
public class MaxSubarrayLength {

    /**
     * 最多 K 个重复元素的最长子数组
     *
     * @param nums 整数数组，需要查找的数组。
     * @param k 目标和，寻找的子数组的元素之和应等于k。
     * @return 返回满足条件的子数组的最大长度；如果不存在满足条件的子数组，则返回0。
     */
    public int maxSubarrayLength(int[] nums, int k) {
        int n = nums.length; // 数组长度
        int r = 0, l = 0; // 右指针r和左指针l，用于标识子数组的起始和结束位置
        int res = 0; // 用于保存结果，即满足条件的子数组的最大长度
        Map<Integer,Integer> mp = new HashMap<>(); // 使用哈希表记录数组元素出现的次数
        // 遍历数组，维护滑动窗口
        while(r < n){
            // 更新右指针元素的出现次数
            mp.put(nums[r], mp.getOrDefault(nums[r], 0) + 1);
            // 当前窗口的和大于k时，缩小窗口
            while(mp.get(nums[r]) > k){
                mp.put(nums[l], mp.get(nums[l]) - 1);
                l++;
            }
            // 更新结果，取最大子数组长度
            res = Math.max(res, r - l + 1);
            r++;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,3,4,5,1,1,1,2,3,1};
        int i = new MaxSubarrayLength().maxSubarrayLength(nums, 2);
        System.out.println(i);
    }
}
